package p234

import node.ListNode
import java.util.*

class StackStragty : Stragty {
    override fun isPalindrome(head: ListNode?): Boolean {
        //链表中间节点
        var root: ListNode? = head
        var fast: ListNode? = head
        var slow: ListNode? = head
        while (fast != null && fast.next != null) {
            fast = fast.next.next
            slow = slow!!.next
        }
        //反转半部分链表
        val stack: Stack<ListNode> = Stack()
        while (slow != null) {
            stack.push(slow)
            slow = slow.next
        }
        //对比
        var tempt: ListNode? = null
        while (!stack.isEmpty() && root != null) {
            tempt = stack.pop()
            if (tempt.`val` != root.`val`) {
                return false
            }
            root = root.next
        }
        return true
    }
}